CSP 2019 提高组游记

注:出门左转参赛总结

声明:蒟蒻第一次打提高组,后面赛场上自然就不会打正解,请大佬勿喷。

Day 0(2019-11-15 Fri.)

下午3:10,翘课出发,东莞-广州

下午4:30 到达广州萝岗万达,入住公寓酒店(27/F)

不用在意上图的人

下午6:10 晚餐

晚上8:00 上洛谷打模板

晚上9:30 集中开会,布置战术

  • 时间安排

  • 注意事项

  • 如何防止爆零

晚上10:00 洗漱

晚上11:00 就寝


Day 1 (2019-11-16 Sat.)

6:30 起床

8:00 到达广州二中

8:30 DAY1 Start!

Day 1 T1:

格雷码?咋一看非常友好,于是着手开始模拟,当我翻到数据范围时我震惊了:

What! k<$2^{64}$?

不管了,先打个模拟先。

天知道我的脑子在干什么,1h都没把模拟打出来,于是开始转战数学方法。

After 30 min….

Go die,不管了,下一题。

~ ~ 请先看完T2 T3 再回来看下面的~ ~

比赛最后30min

猛然想起这格雷码是01串,会不会可以位运算在转二进制输出?

手算了一下,可以!

马上把代码敲好。

但是我再出另外一组数据测时,啊啊啊它错了….

没时间了,算了,去检查源代码文件有没有问题了。

Day 1 T2:

第一眼就看到了树状图,感觉可以爆搜一下,然后就用BFS遍历了一遍搜出所有括号序列,再每种情况统计一遍合法括号组数。

OK 样例过了

打开选手文件,把其他数据丢进来试一试,结果:

T了最后一个….

不管了,先拿部分分。

Day 1 T3:

咋一看我居然看懂了,但没有想到具体要运用哪种算法,不管了,上搜索拿点分先。

距离比赛结束还有30min

…..样例才过了第一组和第三组数据…..

走了走了,回第一题骗分。

12:00 比赛结束

  • 感觉DAY1打的不行啊….明天要努力把分数挣回来….

下午: 休息 上luogu 看番

21:40 集中开会,布置战术

  • 老师:T1应该没人不会吧? 我:默不作声

  • 时间安排

  • …..


Day 2 (2019-11-17 Sun.)

前面省略…..

8:30 DAY2 Start!

Day 2 T1:

哦,做菜?

每道菜做法不相同,主要食材不能超过所用食材一半,问方案数?

哦!DP?

但是多维DP很难搞欸…..

DFS+剪枝!

After 1h…..

完成T1的DFS,样例OK,选手文件夹数据第4、第5,TLE。

可以了,去做T2.

Day 2 T2:

划分?这不是区间DP吗?

于是把区间DP敲了出来。

看了看数据,果断放弃样例3的那种测试点(包括当type=1时的数据)。

先把DP打好,OK,走人!

Day 3 T3:

emmm….树的重心….

什么鬼…反正没多少时间了,那就:

骗分,玄学处理输入。

(具体怎么玄学的我忘了,好像是拿入度和n处理了一下)

拿样例试一试,OK,过了,期望得分5。

12:00 比赛结束

13:50 上车回校

14:55 到达学校

19:00 正常晚修


后记:听说Day 1 T1只用k^=k>>1再转二进制就能过?(看来我的方向没错..)

By C_Cong